「Luogu P3172」[CQOI2015]选数 解题报告

$Link$

求

$$\large \sum_{a_1=L}^H\sum_{a_2=L}^H\cdots\sum_{a_n=L}^H[\gcd\limits_{i=1}^n(a_i)=k]$$

解题思路

莫比乌斯反演 （都是套路

分析

先把 $H$ 用 $R$ 代替，（太难看了

然后就珂以大力推柿子了

先根据套路，把 $k$ 除掉

$$\large \sum_{a_1=\lceil \frac L k \rceil }^{\lfloor \frac R k \rfloor}\cdots\sum_{a_n=\lceil \frac L k \rceil }^{\lfloor \frac R k \rfloor}[\gcd\limits_{i=1}^n(a_i)=1]$$

之后运用反演结论，（还是套路

$$\large \sum_{a_1=\lceil \frac L k \rceil }^{\lfloor \frac R k \rfloor}\cdots\sum_{a_n=\lceil \frac L k \rceil }^{\lfloor \frac R k \rfloor}\sum_{d|\gcd\limits_{i=1}^n(a_i)}\mu(d)$$

改变枚举顺序

$$\large \sum_{d=1}^{\lfloor\frac R k\rfloor}\mu(d)\sum_{a_1=\lceil \frac L k \rceil }^{\lfloor \frac R k \rfloor}d|a_i\cdots\sum_{a_n=\lceil \frac L k \rceil }^{\lfloor \frac R k \rfloor}d|a_n$$

也就是

$$\large \sum_{d=1}^{\lfloor\frac R k\rfloor}\mu(d)\cdot\left(\lfloor\frac{\lfloor \frac R k \rfloor} d \rfloor-\lfloor \frac {\lceil \frac L k \rceil-1} d\rfloor\right)^n$$

于是现在就珂以数论分块求啦

只不过 $\mu(n)$ 貌似线性筛不出来，没关系，杜教筛大法好

时间复杂度

O(能过) $O(n^{\frac 2 3}+\sqrt nlog_2(n))$

Warning

1、杜教筛记得从 $2$ 开始筛

2、数论分块求解时注意 l>L 的情况，此时不能使用 min(L/(L/l),R/(R/L))

3、注意过程中 int 类型的溢出

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rLL rgt LL
#define inf 0x7f7f7f7f
#define p 1000000007
#define N 1000000
#define M 98573
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
int nxt[N],key[N],val[N],head[M];
int L,R,n,t,k,mu[N+3],pr[N],ans,res;
bool v[N+3];
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void Insert(rint k,rint v) {//写了个hash表
    rint c=k%M;key[++t]=k,val[t]=v,nxt[t]=head[c],head[c]=t;
}
inline int Search(rint k) {
    rint c=k%M,i;
    for(i=head[c];i;i=nxt[i])
        if(key[i]==k) return val[i];
    return -1;
}
inline void init() {//预处理杜教筛的前n^{2/3}
    rint i,j,c;mu[1]=1;
    for(i=2;i<=N;++i) {
        if(!v[i]) pr[++t]=i,mu[i]=-1;
        for(j=1;j<=t;++j) {
            c=i*pr[j];if(c>N) break;v[c]=1;
            if(i%pr[j]) mu[c]=-mu[i];
            else break;
        }
    }
    for(i=2;i<=N;++i) mu[i]=(mu[i-1]+mu[i])%p;
}
inline int getmu(rint n) {//杜教筛搞一搞
    if(n<=N) return mu[n];
    rint res=Search(n);
    if(~res) return res;res=1;
    for(rint l=2,r;l<=n;l=r+1) {
        r=n/(n/l);
        res=(res-1ll*(r-l+1)*getmu(n/l))%p;
    }res%=p,Insert(n,res);
    return res;
}
inline int Pow(rLL a) {
    rint b=n;rLL res=1;
    for(;b;a=a*a%p,b>>=1)
    if(b&1) res=res*a%p;return res;
}
inline void solve() {
    if(L%k) L=L/k;//预先除去k
    else L=L/k-1;R/=k;rint x=0,y;//x,y分别记录上次r和本次r的mu函数的前缀和
    for(rint l=1,r;l<=R;l=r+1) {
        if(l<=L) r=min(R/(R/l),L/(L/l));
        else r=R/(R/l);//特判情况
        y=getmu(r),res=Pow(R/l-L/l);
        ans=(ans+1ll*(y-x)*res%p)%p,x=y;
    }printf("%d\n",(ans+p)%p);//可能为负
}
int main()
{
    init(),n=read(),k=read(),
    L=read(),R=read(),solve();
    return 0;
}